#include<bits/stdc++.h>
#define mid (l+r>>1)
#define lc(k) t[k].ls
#define rc(k) t[k].rs
using namespace std;
using ll=long long;
const int N=1e5+5;
const ll inf=1e16;
int n,q;
int l[N],r[N];
struct sgn{
    int ls,rs;
    ll s[3];
    sgn(){}
};
int rt[N];
struct sgt{
    sgn t[N*60];
    int cn;
    void update(int l,int r,int k,int& k1,int x,int op,int d){
        k1=++cn;
        t[k1]=t[k];
        t[k1].s[op]+=d;
        if(l==r)return;
        if(x<=mid){
            update(l,mid,lc(k),lc(k1),x,op,d);
        }
        else{
            update(mid+1,r,rc(k),rc(k1),x,op,d);
        }
    }
    ll query(int l,int r,int k,int k1,int x,int y,int op){
        if(x>y)return 0;
        if(x<=l&&r<=y)return t[k].s[op]-t[k1].s[op];
        if(y<=mid)return query(l,mid,lc(k),lc(k1),x,y,op);
        if(x>mid)return query(mid+1,r,rc(k),rc(k1),x,y,op);
        return query(l,mid,lc(k),lc(k1),x,y,op)+query(mid+1,r,rc(k),rc(k1),x,y,op);
    }
}T;
ll f[N];
ll calc(int l,int r){
    if(l>r)return inf;
    ll ans=0;
    ans+=T.query(1,n,rt[l],0,r,n,0);
    ans+=T.query(1,n,rt[r],rt[l-1],l,r,0)*(r-l)+T.query(1,n,rt[r],rt[l-1],l,r,1)-T.query(1,n,rt[r],rt[l-1],l,r,2);
    ans+=T.query(1,n,rt[r],rt[mid],r+1,n,0)*(r+1)-T.query(1,n,rt[r],rt[mid],r+1,n,1);
    ans+=-T.query(1,n,rt[mid],rt[l],r+1,n,0)*l+T.query(1,n,rt[mid],rt[l],r+1,n,1);
    int md=(l+r+1)>>1;
    ans+=-T.query(1,n,rt[l-1],0,l,md-1,0)*(l-1)+T.query(1,n,rt[l-1],0,l,md-1,2);
    ans+=T.query(1,n,rt[l-1],0,md,r-1,0)*r-T.query(1,n,rt[l-1],0,md,r-1,2);
    return f[l-1]+ans;
}
struct node{
    int l,r;
    int id;
    node(){}
    node(int l,int r,int id):l(l),r(r),id(id){}
};
node qq[N];
int ed;
vector<int> v[N];
int main(){
    freopen("block.in","r",stdin);
    freopen("block.out","w",stdout);
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    cin>>n>>q;
    --n;
    for(int i=1;i<=q;++i){
        int l,r;
        cin>>l>>r;--r;
        v[l].push_back(r);
    }
    for(int i=1;i<=n;++i){
        rt[i]=rt[i-1];
        for(int it:v[i]){
            T.update(1,n,rt[i],rt[i],it,0,1);
            T.update(1,n,rt[i],rt[i],it,1,i);
            T.update(1,n,rt[i],rt[i],it,2,it);
        }
    }
    for(int i=1;i<=n;++i){
        while(ed&&calc(i,qq[ed].l)<calc(qq[ed].id,qq[ed].l))ed--;
        if(ed&&calc(i,qq[ed].r)<calc(qq[ed].id,qq[ed].r)){
            int nl=qq[ed].l-1,nr=qq[ed].r;
            while(nl!=nr){
                int md=nl+nr>>1;
                if(calc(i,md)<calc(qq[ed].id,md))nr=md;
                else nl=md+1;
            }
            qq[ed].r=nl-1;
        }
        if(qq[ed].r!=n){
            int la=qq[ed].r+1;
            qq[++ed]=node(la,n,i);
        }
        int nl=0,nr=ed;
        while(nl!=nr){
            int md=nl+nr>>1;
            if(qq[md].r>=i)nr=md;
            else nl=md+1;
        }
        f[i]=calc(qq[nl].id,i);
    }
    cout<<f[n];
    return 0;
}